from LibJeuDeRockse import *

# Grille de jeu du sujet
T = [[2, -4, -6, 0],
    [1, -2, 2, 3],
    [-2, 2, -3, 4],
    [-1, 4, -3, 7]]

sauts = [(0, 1), (1, -1), (1, 1)]   # Sauts par défaut
bonus = {(1, 2): [(1, 0)]}          # Case bonus en (1,2)

chemin_optimal = [(0, 0), (0, 1), (0, 2), (1, 1), (1, 2), (2, 2), (3, 2), (3, 3)]

####################################
# Partie 1 : Sauts et chemins
####################################


########################################
# Partie 2 : Recherche exhaustive
########################################


########################################
# Partie 3 : Recherche gloutonne
########################################
def trouve_glouton(T,sauts,bonus,k):
    # à compléter

########################################
# Partie 4 : Programmation dynamique
########################################
def code_bonus(masque_bonus):
    return
    # à compléter


def combinaisons_bonus(nb_bonus):
    return
    # à compléter

def trouver_sauts_possibles(sauts,bonus_au_rang,masque_bonus):
    return
    # à compléter

# à compléter
def trouve_dynamique(T,sauts,bonus):
    N = len(T)
    nb_bonus = .......
    nb_code_bonus = 2**nb_bonus
    poids_opt = [[[INFINI for bonus_code in range(nb_code_bonus)]
                          for j in range(N)]
                          for i in range(N)]
    saut_opt = [[[(0,0,0) for bonus_code in range(nb_code_bonus)]
                          for j in range(N)]
                          for i in range(N)]
    (bonus_au_rang ,rang_du_bonus) = ranger_bonus(bonus)
    for bonus_actifs in combinaison_bonus(nb_bonus):
        code_bonus_actifs = code_bonus(bonus_actifs)
        poids_opt[N-1][N-1][code_bonus_actifs] = .....
        sauts_possibles = ........
        for i in range(.......):
            for j in range(......):
                if i == N-1 and j == N-1:
                    continue
                code_bonus_dest = ajouter_bonus(bonus,rang_du_bonus,i,j,
                                         bonus_actifs,code_bonus_actifs)
                if (i,j) in bonus:
                    sauts_possibles_final = sauts_possibles + bonus[(i,j)]
                else:
                    sauts_possibles_final = sauts_possibles
                for (delta_i ,delta_j) in sauts_possibles_final:
                    i_dest = i + delta_i
                    j_dest = j + delta_j
                    if (i_dest in range(N) and j_dest in range(N)):
                        poids_opt_dest = poids_opt[i_dest][j_dest][code_bonus_dest]
                        if (poids_opt[i][j][code_bonus_actifs] > poids_opt_dest):
                            poids_opt[i][j][code_bonus_actifs] = .........
                            saut_opt[i][j][code_bonus_actifs] = ..........
                poids_opt[i][j][code_bonus_actifs] += T[i][j]
    return (poids_opt, saut_opt)

def solution_dynamique(saut_opt,N):
    # à compléter
    return